1. Field of the Invention
The present invention relates to an arithmetic circuit for correcting an approximate value that is computed by the Max-Log-MAP algorithm based on the Log-MAP algorithm.
2. Description of Related Art
In digital communications system, an error correcting code for correcting an error occurring in a transmission line is used. Particularly in mobile communication systems where the radio field intensity varies drastically due to fading and thereby an error is likely to occur, high correction capability is required for error correcting codes. Turbo codes, which are one example of error correcting codes, are notable as the codes having the error correction capability which is close to the Shannon limit and employed in the W-CDMA (Wideband Code Division Multiple Access) or CDMA-2000 as the third-generation mobile communication system, for example. This is disclosed in Japanese Unexamined Patent Application Publications Nos. 2004-80508, 2004-194326, 2002-344330, 2002-100995, and A. Taffin, “Generalized stopping criterion for iterative decoders”, IEEE Electronics Letters, 26 Jun. 2003, Vol. 39, No. 13, for example.
FIG. 15 is a block diagram showing the structure of a typical encoding device for generating turbo codes. The encoding device 101 may be placed on the transmitting side of a communication system in order to encode information bits (systematic bits: systematic portion) U as pre-encoded data into turbo codes as parallel concatenated convolutional codes (PCCCs) and output the turbo codes to the outside such as a transmission line. The turbo codes are not limited to the parallel concatenated convolutional codes and may be any codes which can be turbo-decoded, such as serial concatenated convolutional codes.
The encoding device 101 includes a first encoder 102 and a second encoder 103 which serve as systematic convolutional coders, and an interleaver 104 which interleaves (i.e. rearranges) data as shown in FIG. 15.
The first encoder 102 encodes input systematic portion U to generate redundancy bits (hereinafter as the parity bits) P1 and outputs the parity bits P1 to the outside. The interleaver 104 rearranges each bit of the input systematic portion U into a prescribed interleaved pattern to generate a systematic portion Uint and outputs the generated systematic portion Uint to the second encoder 103. The second encoder 103 encodes the systematic portion Uint to generate parity bits P2 and outputs the parity bits P2 to the outside.
In sum, the encoding device 101 generates the systematic portion U, the parity bits P1, the systematic portion Uint, and the parity bits P2. A pair of the systematic portion U and the parity bits P1 (U, P) is called a first elemental code E, and a pair of the systematic portion Uint and the parity bits P2 (Uint, P2) is called a second elemental code Eint.
The turbo decoding has two features of (1) using a plurality of systematic encoders having a relatively simple and small structure, and (2) each encoder being connected to the information bits as an input to the encoder through the interleaver (rearranging element).
The feature (2) aims to generate different codeword sequences in different encoders by inputting the information bits with rearranged sequences to the encoder. The decoded result of each codeword is thus complemented between the codewords in the decoding side to thereby improve the error correction capability.
The feature (1) aims to use information bits for mutual complementation of decoded results between codewords. For example, the 3GPP (3rd Generation Partnership Project) mandates the use of two 8-state Systematic Convolutional Coders as the feature (1). The 3GPP is working on the standardization of the third-generation mobile communication system such as W-CDMA.
A pair of outputs {U, P1} of an encoder 1 in FIG. 15 is called a first elemental code, and the other pair of outputs {Uint, P2} is called a second elemental code. The bit Uint is not actually output, and three bits of U, P1, and P2 are output to the subsequent stage. Although termination bits are actually output at the same time, they are ignored for simplification of the description. On this account, the coding rate of turbo codes defined by the 3GPP standard is ⅓.
Decoding such encoded turbo codes is called turbo decoding. In the turbo decoding process, decoding is performed iteratively as exchanging extrinsic information between a first decoder for decoding the first elemental code E and a second decoder for decoding the second elemental code Eint. The number of decoders is not limited to two, and two or more stages of decoders may be used in accordance with the number of elemental codes of the turbo codes.
FIG. 16 shows a typical decoding device for turbo decoding. The turbo decoding has one feature of (1) iterating the processing as exchanging the extrinsic information among a plurality of elemental codes.
As shown in FIG. 16, a typical decoding device 201 includes a first decoder 202, a second decoder 203, an interleaved memory 204, a de-interleaved memory 205, and a hard decision/CRC decision section 206.
The turbo decoding process in the decoding device 201 having such a configuration includes the following steps.
(A) Reading extrinsic information of the second decoder 203 from the de-interleaved memory 205 and inputting the extrinsic information and a first elemental code to the first decoder 202. Then, outputting extrinsic information from the first decoder 202 and writing it to the interleaved memory 204.(B) Reading the extrinsic information of the first decoder 202 from the interleaved memory 204 and inputting the extrinsic information and a second elemental code to the second decoder 203. Then, outputting extrinsic information from the second decoder 203 and writing it to the de-interleaved memory 205.(C) In the final iteration of the decoding process, reading a log likelihood ratio LLR of the second decoder 203 from the de-interleaved memory 205, making the hard decision in the hard decision/CRC decision section 206, and finally performing error checking by CRC.
In the turbo decoding process, the step (A) is performed first. The extrinsic information from the second decoder 203 is an initial value (=0) in this step. Then, the step (B) is performed and further the step (A) is performed again. Subsequently, the steps (B) and (A) are iterated an arbitrary number of times. In the final iteration, the step (B) is performed. At this step, the second decoder 203 outputs the log likelihood ratio rather than the extrinsic information. After that, the step (C) is performed finally.
Because the turbo codes are systematic bits, the information bits U are contained in a received sequence. The extrinsic information is a value (priori value) indicating the likelihood of “0” (equivalent with the likelihood of “1”), which is predefined for the information bits U prior to the decoding. The turbo decoding is the process that exchanges (mutually complements) the probability that each information bit is “0” in the decoding between the first and second elemental codes to thereby improve the accuracy of the probability and enhance the error correction capability.
The extrinsic information can be generated from the output of a soft-output decoder (log likelihood ratio LLR). There are two types of generating the soft output: MAP and SOVA. The MAP algorithm is generally more widely used because of its higher error correction capability. MAP, Log-MAP, and Max-Log-MAP are mainly known as the MAP algorithm.
Prior to describing the MAP, Log-MAP, and Max-Log-MAP algorithms, the log likelihood ratio LLR is described hereinbelow. Just like the extrinsic information, the log likelihood ratio LLR also indicates the likelihood of “0” of the information bits U. Though the extrinsic information is a priori value, the log likelihood ratio LLR is called a posteriori value. The log likelihood ratio is represented by the following Expression 1:
Log likelihood ratio:
                              L          ⁡                      (                          u              k                        )                          =                  log          ⁡                      (                                          P                ⁡                                  (                                                            u                      k                                        =                                                                  +                        1                                            |                      y                                                        )                                                            P                ⁡                                  (                                                            u                      k                                        =                                                                  -                        1                                            |                      y                                                        )                                                      )                                              (        1        )            whereP( ) indicates a probability,uk indicates a k-th information bit,y indicates a received sequence,P(uk=+1|y) indicates a probability that the k-th information is +1(=“0”) when receiving the received sequence y, andP(uk=−1|y) indicates a probability that the k-th information is −1(=“1”) when receiving the received sequence y.ûk=sign[L(uk)]  (2)where sign [ ] indicates a hard decision.
The log likelihood ratio LLR is represented by Expression 1. In this expression, “0” is represented by +1, and “1” is represented by −1. The log ratio of the probability of being “0” and the probability of being “1” is used to obtain a likelihood which indicates either “0” or “1” is more likely. If the probability of being “0” is higher than the probability of being “1”, the ratio of those probabilities is larger than 1, and the log ratio is larger than 0 (positive number). On the other hand, if the probability of being “1” is higher than the probability of being “0”, the ratio of those probabilities is a value below the decimal point which is less than 1, and the log ratio is smaller than 0 (negative number). Accordingly, the probability of being either “0” or “1” can be determined from the sign (positive or negative) of the log likelihood ratio. If the probability of being “0” and the probability of being “1” are equal, their ratio is 1 and the log ratio is 0, thus being unclear as to which probability is higher.
Expression 2 represents the log likelihood ratio LLR in regard to the k-th information bit uk. The uk in Expression 2 is an estimate for the k-th information bit in the receiving side, which is a result of the hard decision of LLR (=“0” or “1”). The hard decision sign[ ] is the processing of retrieving a sign binary bit, and it indicates “0” if the value is positive or “1” if the value is negative. Therefore, Expression 2 represents the hard decision of LLR for the k-th information bit.
The MAP, Log-MAP, and Max-Log-MAP algorithms are described hereinafter.
MAP (Maximum A Posteriori Probability) Algorithms
MAP, which stands for Maximum A posteriori Probability, is a decoding algorithm for maximizing LLR that is a posteriori value (A posteriori probability) and also called a posteriori probability maximization decoding.
The MAP algorithm calculates a log likelihood ratio L(uk) using the following Expression 3 which is a result of several formula conversions on the above Expression (1). In this expression, γ indicates a transition probability of trellis, α indicates an achievement probability to each state of trellis upon transition from the starting point to the endpoint, and β indicates an achievement probability from the endpoint reversely. The trellis is a state transition diagram of an encoder deployed on the time base. This is called a trellis diagram.
Log likelihood ratio
                              L          ⁡                      (                          u              k                        )                          =                  log          ⁡                      (                                                            ∑                                      S                    +                                                  ⁢                                                                                                    α                        ~                                                                    k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ·                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ·                        s                                            )                                                        ·                                                                                    β                        ~                                            k                                        ⁡                                          (                      s                      )                                                                                                                    ∑                                      S                    -                                                  ⁢                                                                                                    α                        ~                                                                    k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ·                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ·                        s                                            )                                                        ·                                                                                    β                        ~                                            k                                        ⁡                                          (                      s                      )                                                                                            )                                              (        3        )            
In the MAP algorithm, Viterbi decoding is performed using the trellis diagram (state transition diagram). The path connecting each state at each time point on the trellis diagram corresponds to the coded sequence to be decoded. The likelihood (path metric) for the possible path is calculated, and the path with the highest likelihood is decoded as a survival path.
The trellis diagram is described first of all. FIG. 17 is a view showing a recursive convolutional encoder for outputting recursive convolutional codes. FIG. 18 is a schematic diagram showing the state transition thereof.
In the recursive convolutional encoder, the values stored in D1 and D2 vary by input bits supplied through the input INPUT. In the recursive encoder, the output of D2 is forwarded to the input INPUT side, thereby realizing the recursive convolutional encoding. FIG. 18 shows the state transition diagram of the possible values of the D1 and D2, i.e. (00), (01), (10), and (11) In FIG. 18, 0/0 indicates input bit/output bit, for example. The values of D1 and D2 transit according to the input bits “0” or “1” through the input INPUT. For example, when (D1 D2) is (00), the convolutional encoder outputs “0” through the output OUTPUT if “0” is input through the input INPUT, and the D1 and D2 return to the state (00). If, on the other hand, “1” is input, the convolutional encoder outputs “1”, and the D1 and D2 shift to the state (10).
FIG. 19 is a trellis diagram that the state transition diagram of FIG. 18 is deployed on the time base. In FIG. 19, the full-line arrow indicates the state transition of D1 and D2 when the input bit is “0”, and the dotted-line arrow indicates the state transition of D1 and D2 when the input bit is “1”. The horizontal axis represents the time base, and k−1 and k indicate given timings.
The process of performing Viterbi decoding in the forward direction on the trellis diagram to thereby calculate a path metric is called the forward process. The process of performing Viterbi decoding in the opposite direction from the forward process to thereby calculate a path metric is called the backward process. A path metric value which is calculated in the forward process is called a path metric, and a path metric value which is calculated in the backward process is called β path metric. γ indicates the probability of transition from a certain state (e.g. state (11)) at timing (k−1) to a certain state (e.g. state (11)) at timing k, which is called branch metric. The values α and β indicate the probability of being the relevant state (e.g. state (11)) at timings (k−1) and k. A log likelihood ratio LLR is calculated from the α path metric, the β path metric, and the branch metric (γ).
FIG. 20 is a view to describe the way of calculating the transition probability using the trellis diagram. The calculation formula for the values α and β are shown below as Expressions 4 and 5. As described above, the value γ indicates the transition probability in each state at a certain time point on the trellis. The value α, which is represented by the following Expression 4, indicates the achievement probability to each state in the forward direction (i.e. the direction from the starting point to the endpoint on the trellis diagram), and it is the summation of γ in the forward direction. The value β, which is represented by the following Expression 5, is the summation of γ in the backward direction (i.e. the direction from the endpoint to the starting point).
                              Achievement          ⁢                                          ⁢                      probability            :                                                            α                  ~                                k                            ⁡                              (                s                )                                                    =                              ∑                                          x                ′                            ∈              s                                ⁢                                                                      α                  ~                                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                      ·                                          γ                k                            ⁡                              (                                                      s                    ′                                    ,                  S                                )                                                                        (        4        )                                          Achievement          ⁢                                          ⁢                      probability            :                                                            β                  ~                                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                                    =                              ∑                                          x                ′                            ∈              s                                ⁢                                                                      α                  ~                                                  k                  -                  1                                            ⁡                              (                s                )                                      ·                                          γ                k                            ⁡                              (                                                      s                    ′                                    ,                  S                                )                                                                        (        5        )            
If, for example, αk(00) indicates the achievement probability in the forward direction existing in the state (00) at timing k (which is referred to hereinafter as the state (00)k), αk (00) is a sum of a product of αk-1 (00) and a transition probability γk (00, 00) from the achievement probability αk-1 (00) in the state (00)k-1 to the state (00)k and a product of the achievement probability αk-1(01) in the state (01)k-1 and a transition probability γk(01, 00) from the state (00)k-1 to the state (00)k, as shown in FIG. 20 and Expression 4.
Further, if βk-1(00) indicates the achievement probability in the backward direction existing in the state (00) at timing k−1 (which is referred to hereinafter as the state (00)k-1), βk-1(00) is a sum of a product of βk-1(00) and a transition probability γk(00, 00) from the achievement probability βk-1(00) in the state (00)k-1 to the state (00)k and a product of the achievement probability βk-1(01) in the state (01)k-1 and a transition probability γk(00, 10) from the state (00)k-1 to the state (10)k, as shown in FIG. 20 and Expression 5.
In Expressions 4 and 5, α(s) and β(s) indicate the path metric in the present state s and the previous state s′, and γ(s′, s) indicates the probability of state transition from s′ to s.
FIG. 21 is a view to describe the way of calculating the log likelihood ratio LLR from the values α, β, and γ. As shown in FIG. 21, the multiplication of the achievement probability α in the forward direction, the achievement probability β in the backward direction, and the transition probability γ between states gives the transition probability at the relevant time point in consideration of all time points on the trellis. The product of the transition probability corresponding to the input “0” is δ0, and the product of the transition probability corresponding to the input “1” is δ1. The log ratio of δ0 and δ1, i.e. log(δ0/δ1), is the log likelihood ratio LLR represented by the above Expression 3.
The log likelihood ratio and the extrinsic information satisfy the following Expression 6. Specifically, the turbo decoding process calculates the extrinsic information by subtracting intrinsic information from both sides of Expression 6 representing the log likelihood ratio LLR.
Log Likelihood Ratio:
                              L          ⁡                      (                          u              k                        )                          =                                            L              c                        ⁢                          y              k              s                                +                                    L              e                        ⁡                          (                              u                k                            )                                +                      log            ⁡                          (                                                                    ∑                                          S                      +                                                        ⁢                                                                                                              α                          ~                                                                          k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              ·                                                                  γ                        k                        e                                            ⁡                                              (                                                                              s                            ′                                                    ·                          s                                                )                                                              ·                                                                                            β                          ~                                                k                                            ⁡                                              (                        s                        )                                                                                                                                  ∑                                          S                      -                                                        ⁢                                                                                                              α                          ~                                                                          k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              ·                                                                  γ                        k                        e                                            ⁡                                              (                                                                              s                            ′                                                    ·                          s                                                )                                                              ·                                                                                            β                          ~                                                k                                            ⁡                                              (                        s                        )                                                                                                        )                                                          (        6        )            whereLc indicates a constant determined by a transmission line,yks indicates a systematic portion,Le(uk) indicates previous extrinsic information (priori information),Lcyks+Le(uk) indicates intrinsic information, and
  log  ⁡      (                            ∑                      S            +                          ⁢                                                            α                ~                                            k                -                1                                      ⁡                          (                              s                ′                            )                                ·                                    γ              k              e                        ⁡                          (                                                s                  ′                                ·                s                            )                                ·                                                    β                ~                            k                        ⁡                          (              s              )                                                            ∑                      S            -                          ⁢                                                            α                ~                                            k                -                1                                      ⁡                          (                              s                ′                            )                                ·                                    γ              k              e                        ⁡                          (                                                s                  ′                                ·                s                            )                                ·                                                    β                ~                            k                        ⁡                          (              s              )                                            )  indicates extrinsic information.Log-MAP Algorithm
The Log-MAP algorithm is described below. As described above, the MAP algorithm calculates the product of the probabilities and therefore it requires a multiplier, which causes a significant increase in circuit size. Thus, in actual applications, the Log-MAP or Max-log-MAP algorithm which approximates or simplifies the probability calculation in the MAP algorithm in a log region is employed. The approximate expressions are shown in the following Expressions 7 to 11.
                                          A            k                    ⁡                      (            s            )                          =                  log          ⁢                                          ⁢                                                    α                ~                            k                        ⁡                          (              s              )                                                          (        7        )                                                      B            k                    ⁡                      (            s            )                          =                  log          ⁢                                          ⁢                                                    β                ~                            k                        ⁡                          (              s              )                                                          (        8        )                                                      Γ            k                    ⁡                      (                                          s                ′                            ,              s                        )                          =                  log          ⁢                                          ⁢                                                    γ                ~                            k                        ⁡                          (                                                s                  ′                                ,                s                            )                                                          (        9        )                                                      A            k                    ⁡                      (            s            )                          =                  log          (                                    ∑                              x                ′                                      ⁢                          exp              ⁡                              (                                                                            A                                              k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        +                                                            Γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                                      )                                              )                                    (        10        )                                                      B                          k              -              1                                ⁡                      (            s            )                          =                  log          (                                    ∑              x                        ⁢                          exp              ⁡                              (                                                                            B                      k                                        ⁡                                          (                      s                      )                                                        +                                                            Γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                                      )                                              )                                    (        11        )            
The values α, γ, β are approximated by a log and defined as A, Γ, and B, respectively, as shown in Expressions 7 to 9 to thereby give Expressions 10 and 11 which are transformed versions of Expressions 4 and 5. However, Expressions 10 and 11 contain the items that the replacement of the calculation inside the parentheses exp. with Ai results in Expression 12 below, which poses a problem in actual applications. Thus, Expression 12 is further decomposed into Expression 13 below.
                    log        [                              ∑            i                    ⁢                      exp            ⁡                          (                              A                i                            )                                      ]                            (        12        )                                                                                                      log                  [                                                            ∑                      i                                        ⁢                                          exp                      ⁡                                              (                                                  A                          i                                                )                                                                              ]                                =                                                      A                    M                                    +                                      log                    (                                          1                      +                                                                        ∑                                                                                    A                              i                                                        ≠                                                          A                              M                                                                                                      ⁢                                                  exp                          ⁡                                                      (                                                          -                                                                                                                                                                    A                                    i                                                                    -                                                                      A                                    M                                                                                                                                                                                        )                                                                                                                )                                                              ,                                                                                          A                M                            =                                                max                  i                                ⁢                                                                  ⁢                                  A                  i                                                                                        (        13        )            
In the above expressions, the value i indicates the number of paths which transit to a certain state. In the example of FIG. 20, the number of paths which transit to the state (00)k in the forward direction is 2, and AM indicates the larger one of the paths. In actuality, the calculation is performed on the basis of Expression 13. This is the Log-MAP algorithm. Particularly, a typical technique implements decoding with LUT by setting the second term of the right side of Expression 13 to log(1+e−x). A technique of making a further approximation with a fixed value or −ax+b is also known. The operation of log(1+e−x) addition is sometimes particularly called Log-sum. The item |Ai−AM| in the second term is called the path metric value.
MAX-Log-MAP Algorithm
The Max-Log-MAP algorithm is a technique that further approximates the Log-MAP algorithm which is represented by Expressions 10 and 11 above. The approximate expressions are shown as the following Expressions 14 and 15. Specifically, in the Max-Log-MAP algorithm, the Log-sum term is eliminated from the above Expressions 10 and 11. The item max( ) is the operation for selecting a maximum value, which is equivalent with ACS (Add Compare Select) operation in the Viterbi Algorithm. Therefore, this is a simple method with a lowest cost which enables the probability calculation to be performed using the Viterbi Algorithm.
                                                                                          A                  k                                ⁡                                  (                  s                  )                                            =                            ⁢                              log                (                                                      ∑                                          s                      ′                                                        ⁢                                      exp                    ⁢                                          {                                                                                                    A                                                          k                              -                              1                                                                                ⁡                                                      (                                                          s                              ′                                                        )                                                                          +                                                                              Γ                            k                                                    ⁡                                                      (                                                                                          s                                ′                                                            ,                              S                                                        )                                                                                              }                                                                      )                                                                                        ≈                            ⁢                                                max                  i                                ⁢                                  (                                                                                    A                                                  k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              +                                                                  Γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                                              )                                                                                        (        14        )                                                                                                      B                                      k                    -                    1                                                  ⁡                                  (                  s                  )                                            =                            ⁢                              log                (                                                      ∑                    s                                    ⁢                                      exp                    ⁢                                          {                                                                                                    B                            k                                                    ⁡                                                      (                            s                            )                                                                          +                                                                              Γ                            k                                                    ⁡                                                      (                                                                                          s                                ′                                                            ,                              S                                                        )                                                                                              }                                                                      )                                                                                        ≈                            ⁢                                                max                  i                                ⁢                                  (                                                                                    B                        k                                            ⁡                                              (                        s                        )                                                              +                                                                  Γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                                              )                                                                                        (        15        )            
As described above, the probability calculation in the Log-MAP algorithm is equivalent to making a correction with Log-sum (referred to hereinafter as the Jacobian correction factor) to the ACS operation in the Viterbi Algorithm. FIG. 22 schematically shows a circuit for performing the probability calculation using the Log-MAP algorithm. As shown in FIG. 22, a circuit 301 for performing the calculation as represented by Expression 13 includes an ACS circuit 302 that compares input values to select and output the larger one and a Log-Sum circuit 303 that obtains the Jacobian correction factor and calculates a sum with the operation results of the ACS circuit 302.
The ACS circuit 302 receives two Ai, which are referred to hereinafter as input I1 and input I2. The ACS circuit 302 includes an adder 311 that adds the input I1 and an inverted value of the input I2, a selector 312, and an absolute value circuit 313. The adder 311 adds the input I1 and an inverted value of the input I2, determines which value of the inputs I1 and I2 is larger according to the result being positive or negative, and supplies the determination result to the selector 312. According to the determination result, the selector 312 selects and outputs the larger one (=AM) of the inputs I1 and I2. The absolute value circuit 313 outputs an absolute value of the result of the adder 311, which is a difference between the inputs I1 and I2. This value is the path metric value |Ai−AM| in the above Expression 13.
The Log-Sum circuit 303 calculates log(l+e^(−|Ai−AM|)) based on the above value. The calculation of the correction factor may be performed using the approximate expression with a fixed value or −ax+b, or using LUT with log(1+e−x). After that, an adder 321 adds the obtained result and the output AM from the ACS circuit 302 and outputs the result s.
The above techniques, however, require the implementation of LUT or the implementation of a circuit for multiplication and addition contained in the approximate expression, which causes an increase in circuit size and data path delay. If a Log-sum correction factor can be calculated using a simple circuit with the bit operation of x only without implementing LUT or a multiplication/addition circuit, the provision of a decoding device with a smaller circuit and less delay would be enabled.